﻿using System;
using System.Collections.Generic;
using System.Threading;

namespace Flagwind.Data
{
	/// <summary>
	/// 最热访问的名-值 对管理对象，节点被访问的次数越多，越容易被访问到的数据结构。
	/// </summary>
	internal class NameValueDictionary<T> : IDictionary<string, T>
	{
		#region 私有常量

		private const int MAX_COUNT = 0xffff;

		#endregion

		#region 私有字段

		private readonly int _hotSize = 3;
		private int _count = 0; // 元素的有效数量
		private int _seekIndex = 0; // 发现目标的位置,仅供参考
		private readonly object _lock = new object();
		private DataItem[] _dataItems = new DataItem[MAX_COUNT];
		private int[] _hotData;
		private readonly List<DataItem> _extList = new List<DataItem>();
		private readonly HexUtility _hexStringBuffer = new HexUtility();
		private readonly Queue<int> _freeQueue = new Queue<int>(); //空闲位置队列

		#endregion

		#region 公共属性

		/// <summary>
		/// 发现目标的位置。
		/// </summary>
		public int At
		{
			get
			{
				return _seekIndex;
			}
		}

		/// <summary>
		/// 容器已经存储的元素总数量。
		/// </summary>
		public int Count
		{
			get
			{
				return _count;
			}
		}

		/// <summary>
		/// 容量大小，默认是64K，不可设置比这个数更大的值。容器超过这个容量，则容量外的很少使用的元素将被移除。
		/// </summary>
		public int Capacity
		{
			get;
			set;
		}

		/// <summary>
		/// (键)碰撞的数量
		/// </summary>
		public int CollidedCount
		{
			get
			{
				return _extList.Count;
			}
		}

		#endregion

		#region 构造方法

		/// <summary>
		/// 初始化 HotNameValue 类的新实例。
		/// </summary>
		public NameValueDictionary()
		{
			this.Init();
		}

		/// <summary>
		/// 初始化热点数据大小，不能大于64，建议在10以内。
		/// </summary>
		/// <param name="size"></param>
		public NameValueDictionary(int size)
		{
			if(size < 64 && size > 0)
			{
				_hotSize = size;
			}
			this.Init();
		}

		#endregion

		#region 公共方法

		/// <summary>
		/// 获取扩展列表中的下一个空闲位置写入新的数据。
		/// </summary>
		/// <returns>位置索引。</returns>
		private int SetDataOnFreeIndex(ref DataItem data)
		{
			lock(_lock)
			{
				int index = 0;
				if(_freeQueue.Count > 0)
				{
					index = _freeQueue.Dequeue();
					_extList[index] = data;
				}
				else
				{
					index = _extList.Count;
					_extList.Add(data);
				}
				_count++;
				return index;
			}
		}

		/// <summary>
		/// 查找指定的键的值，如果找不到将抛出异常。
		/// </summary>
		/// <param name="key">指定的键。</param>
		/// <returns>指定的键的值。</returns>
		public T Get(string key)
		{
			_seekIndex = -1;
			T result;
			if(GetFromHot(key, out result))
			{
				return result;
			}
			int p = _hexStringBuffer.String2Int(key);
			//未碰撞
			if(_dataItems[p].Key == key)
			{
				_seekIndex = p;
				_dataItems[p].AddReadCount();
				//更新热点
				UpdateHot(p);
				return _dataItems[p].Value;
			}
			else
			{
				if(_dataItems[p].Key == null)
				{
					throw new ArgumentException("指定的键[" + key + "]未找到！（内部错误位置：1）");
				}
				int index = _dataItems[p].ExtNext;
				//碰撞，根据完整的名字在链表中找到目标
				while(index > 0)
				{
					if(_extList[index].Key == key)
					{
						_seekIndex = p;
						var objData = _extList[index];
						objData.AddReadCount();
						_extList[index] = objData;
						return objData.Value;
					}
					index = _extList[index].ExtNext;
				}
				if(index == 0)
				{
					throw new ArgumentException("指定的键[" + key + "]未找到！（内部错误位置：2）");
				}
			}
			throw new ArgumentException("指定的键[" + key + "]未找到！（内部错误位置：3）");
		}

		/// <summary>
		/// 查找指定的键的值，但是找不到不抛出异常。
		/// </summary>
		/// <param name="key">指定的键。</param>
		/// <param name="result">指定的键的值。</param>
		/// <returns>查找是否成功。</returns>
		public bool TryGet(string key, out T result)
		{
			_seekIndex = -1;
			result = default(T);
			if(GetFromHot(key, out result))
			{
				return true;
			}
			int p = _hexStringBuffer.String2Int(key);
			if(_dataItems[p].Key == null)
			{
				return false;
			}
			//未碰撞
			if(_dataItems[p].Key == key)
			{
				_seekIndex = p;
				_dataItems[p].AddReadCount();
				result = _dataItems[p].Value;

				//更新热点
				this.UpdateHot(p);
				return true;
			}
			else
			{
				int index = _dataItems[p].ExtNext;

				// 碰撞，根据完整的名字在链表中找到目标
				// extList 不会收缩，可以确保 extList[index] 不会为空，线程安全
				while(index > 0)
				{
					if(_extList[index].Key == key)
					{
						_seekIndex = p;

						var objData = _extList[index];
						objData.AddReadCount();
						result = objData.Value;
						_extList[index] = objData;
						return true;
					}
					index = _extList[index].ExtNext;
				}
			}
			return false;
		}

		/// <summary>
		/// 设置指定键的值，如果存在，则替换
		/// </summary>
		/// <param name="key"></param>
		/// <param name="value"></param>
		public void Set(string key, T value)
		{
			int p = _hexStringBuffer.String2Int(key);
			//检查是否有碰撞
			//下面的判断类似于 下面的功能，但是线程安全
			//if (dataArr[p].Key == null)
			//{
			//    dataArr[p].Key = key;
			//    dataArr[p].Value = value;
			//}
			if(Interlocked.CompareExchange(ref _dataItems[p].Key, key, null) == null)
			{
				_dataItems[p].Value = value;
				Interlocked.Increment(ref _count);
			}
			else
			{
				if(_dataItems[p].Key == key) //未碰撞，此时应该更新值
				{
					_dataItems[p].Value = value;
				}
				else
				{
#if(LockFree)
	//发生碰撞，更新节点指针 ExtNext
                    DataItem data = new DataItem();
                    data.Key = key;
                    data.Value = value;
                    int index = SetDataOnFreeIndex(ref data);
                    
                    if (Interlocked.CompareExchange(ref dataArr[p].ExtNext, index, 0) > 0)
                    {
                        //碰撞的数大于2个
                        lock (sync_obj)
                        {
                            int extIndex = dataArr[p].ExtNext;
                            while (extList[extIndex].ExtNext > 0)
                            {
                                extIndex = extList[extIndex].ExtNext;
                            }
                            //注意：
                            //List<T> 中的结构体，直接修改或者调用方法，无效，但是数组可以
                            //所以需要重新整体赋值
                            DataItem objData = extList[extIndex];
                            objData.ExtNext = index;
                            extList[extIndex] = objData;
                        }
                    }
                
#else
					lock(_lock)
					{
						//发生碰撞，更新节点指针 ExtNext
						DataItem data = new DataItem();
						data.Key = key;
						data.Value = value;
						_extList.Add(data);
						int index = _extList.Count - 1;
						if(_dataItems[p].ExtNext > 0)
						{
							int extIndex = _dataItems[p].ExtNext;
							while(_extList[extIndex].ExtNext > 0)
							{
								extIndex = _extList[extIndex].ExtNext;
							}
							DataItem objData = _extList[extIndex];
							objData.ExtNext = index;
							_extList[extIndex] = objData;
						}
						else
						{
							_dataItems[p].ExtNext = index;
						}
						_count++;
					}
#endif
				}
			}
		}

		#endregion

		#region 私有方法

		private void Init()
		{
			this.Capacity = MAX_COUNT;

			_extList.Add(new DataItem());
			_hotData = new int[_hotSize];
			for(int i = 0; i < _hotData.Length; i++)
			{
				_hotData[i] = -1;
			}
		}

		private bool GetFromHot(string key, out T result)
		{
			for(int i = 0; i < _hotSize; i++)
			{
				int p = _hotData[i];
				if(p == -1)
				{
					continue;
				}
				//未碰撞
				if(_dataItems[p].Key == key)
				{
					_seekIndex = p;
					_dataItems[p].AddReadCount();
					result = _dataItems[p].Value;
					return true;
				}
			}
			result = default(T);
			return false;
		}

		private void UpdateHot(int obj)
		{
			int readCount = _dataItems[obj].ReadCount;
			for(int i = 0; i < _hotSize; i++)
			{
				int p = _hotData[i];
				if(p == -1)
				{
					_hotData[i] = obj;
					break;
				}
				else
				{
					if(_dataItems[p].ReadCount < readCount)
					{
						_hotData[i] = obj;
						break;
					}
				}
			}
		}

		#endregion

		#region 内部结构

		/// <summary>
		/// 数据项。
		/// </summary>
		private struct DataItem
		{
			#region 私有字段

			private T _value;

			#endregion

			#region 公共属性

			/// <summary>
			/// 原始的 Key, 可能跟散列的Key不一致，发生Key碰撞。
			/// </summary>
			public string Key;

			/// <summary>
			/// 获取或者设置值，线程安全。
			/// </summary>
			public T Value
			{
				get
				{
					return _value;
				}
				set
				{
					_value = value;
					//调用内存栅栏，使得后面的读线程能够立即读取到最新的值
					Thread.MemoryBarrier();
				}
			}

			public int ReadCount;

			/// <summary>
			/// 如果Key发生碰撞，那么新的节点的位置。
			/// </summary>
			public int ExtNext;

			#endregion

			#region 公共方法

			public void AddReadCount()
			{
				Interlocked.Increment(ref this.ReadCount);
			}

			#endregion
		}

		#endregion

		#region IDictionary<string,T> 成员

		public void Add(string key, T value)
		{
			Set(key, value);
		}

		public bool ContainsKey(string key)
		{
			T data;
			return TryGet(key, out data);
		}

		public ICollection<string> Keys
		{
			get
			{
				int allCount = _count + _extList.Count;
				string[] result = new string[allCount];
				int index = allCount - 1;
				for(int i = 0; i < MAX_COUNT; i++)
				{
					if(_dataItems[i].Key != null)
					{
						result[index--] = _dataItems[i].Key;
					}
				}
				for(int i = 0; i < _extList.Count; i++)
				{
					if(_extList[i].Key != null)
					{
						result[index--] = _extList[i].Key;
					}
				}
				string[] temp = new string[allCount - index];
				if(index == 0)
				{
					return temp;
				}
				else
				{
					result.CopyTo(temp, index);
					return temp;
				}
			}
		}

		public bool Remove(string key)
		{
			int p = _hexStringBuffer.String2Int(key);
			//检查是否有碰撞
			if(_dataItems[p].Key == null) //没有对应的数据
			{
				return false;
			}
			else
			{
				if(_dataItems[p].Key == key) //未碰撞，此时应该更新值
				{
					_dataItems[p].Value = default(T);
					_dataItems[p].ReadCount = 0;
					//ExtNext 不可更新
					return true;
				}
				else
				{
					//发生碰撞，更新节点指针 ExtNext
					lock(_lock)
					{
						int index = _dataItems[p].ExtNext;
						if(index > 0)
						{
							List<int> keyIndexList = new List<int>();
							int objIndex = 0;
							while(index > 0)
							{
								keyIndexList.Add(index);
								if(_extList[index].Key == key)
								{
									objIndex = index;
									break;
								}
								else
								{
									index = _extList[index].ExtNext;
								}
							}
							if(objIndex > 0)
							{
								if(keyIndexList.Count >= 1)
								{
									int nextIndex = _extList[objIndex].ExtNext;
									if(nextIndex > 0 || keyIndexList.Count > 1)
									{
										if(keyIndexList.Count > 1)
										{
											int preIndex = keyIndexList[keyIndexList.Count - 2];
											var preData = _extList[preIndex];
											preData.ExtNext = nextIndex;
											_extList[preIndex] = preData;
										}
										else
										{
											//修正入口位置
											_dataItems[p].ExtNext = nextIndex;
										}
									}
									else
									{
										//当前节点没有下一个节点，将入口位置置为0
										_dataItems[p].ExtNext = 0;
									}
									//如果没有下一节点，直接将当前节点移除
									_extList[objIndex] = new DataItem();
									_freeQueue.Enqueue(objIndex);
								}
								return true;
							}
						}
					}
				}
			}
			return false;
		}

		public bool TryGetValue(string key, out T value)
		{
			return TryGet(key, out value);
		}

		public ICollection<T> Values
		{
			get
			{
				List<T> result = new List<T>();
				for(int i = 0; i < MAX_COUNT; i++)
				{
					if(_dataItems[i].Key != null)
					{
						result.Add(_dataItems[i].Value);
					}
				}
				for(int i = 0; i < _extList.Count; i++)
				{
					if(_extList[i].Key != null)
					{
						result.Add(_extList[i].Value);
					}
				}
				return result;
			}
		}

		public T this[string key]
		{
			get
			{
				return Get(key);
			}
			set
			{
				Set(key, value);
			}
		}

		#endregion

		#region ICollection<KeyValuePair<string,T>> 成员

		public void Add(KeyValuePair<string, T> item)
		{
			Set(item.Key, item.Value);
		}

		public void Clear()
		{
			_dataItems = new DataItem[MAX_COUNT];
			for(int i = 0; i < _extList.Count; i++)
			{
				DataItem data = _extList[i];
				data.Value = default(T);
				_extList[i] = data;
			}
		}

		public bool Contains(KeyValuePair<string, T> item)
		{
			T data = Get(item.Key);
			return data.Equals(item.Value);
		}

		public void CopyTo(KeyValuePair<string, T>[] array, int arrayIndex)
		{
			int index = 0;
			if(arrayIndex < 0)
			{
				arrayIndex = 0;
			}
			for(int i = 0; i < MAX_COUNT; i++)
			{
				if(_dataItems[i].Key != null && index >= arrayIndex)
				{
					KeyValuePair<string, T> item = new KeyValuePair<string, T>(_dataItems[i].Key, _dataItems[i].Value);
					array[index++] = item;
				}
			}
			for(int i = 0; i < _extList.Count; i++)
			{
				if(_extList[i].Key != null && index >= arrayIndex)
				{
					KeyValuePair<string, T> item = new KeyValuePair<string, T>(_extList[i].Key, _extList[i].Value);
					array[index++] = item;
				}
			}
		}

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		public bool Remove(KeyValuePair<string, T> item)
		{
			return Remove(item.Key);
		}

		#endregion

		#region IEnumerable<KeyValuePair<string,T>> 成员

		public IEnumerator<KeyValuePair<string, T>> GetEnumerator()
		{
			for(int i = 0; i < MAX_COUNT; i++)
			{
				if(_dataItems[i].Key != null)
				{
					yield return new KeyValuePair<string, T>(_dataItems[i].Key, _dataItems[i].Value);
				}
			}
			for(int i = 0; i < _extList.Count; i++)
			{
				if(_extList[i].Key != null)
				{
					yield return new KeyValuePair<string, T>(_extList[i].Key, _extList[i].Value);
				}
			}
		}

		#endregion

		#region IEnumerable 成员

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			for(int i = 0; i < MAX_COUNT; i++)
			{
				if(_dataItems[i].Key != null)
				{
					yield return _dataItems[i].Value;
				}
			}
			for(int i = 0; i < _extList.Count; i++)
			{
				if(_extList[i].Key != null)
				{
					yield return _extList[i].Value;
				}
			}
		}

		#endregion
	}
}